\chapter{Algoritma Divide and Conquer}


\ifthenelse{\boolean{adaTIU}}{
	\begin{footnotesize}
	  \begin{description}
	    \item[Tujuan Pembelajaran]:
			\begin{itemize}
				\item Memberikan penjelasan tentang teknik Divide and Conquer dan masalah yang dapat diselesaikan dengan teknik tersebut
				\item Memberikan penjelasan algoritma Pengurutan yang menggunakan teknik Divide and Conquer
				\item Memberikan penjelasan algoritma Pencarian yang menggunakan teknik Divide and Conquer
			\end{itemize}
			\item[Setelah menyelesaikan modul ini mahasiswa diharapkan dapat]:
			\begin{itemize}
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Pengurutan Gabung 
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Pengurutan Cepat 
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Pencarian Biner
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas pencarian tinggi Binary Tree
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas traversing pada Binary Tree
			\end{itemize}
			\item[Kata kunci]:
			Pencarian Biner, Pengurutan Cepat, Pengurutan Gabung, Taversing, Teknik Divide and Conquer
	  \end{description}
	\end{footnotesize}
}


\section{Pendahuluan}

Dalam bab sebelumnya kita membahas beberapa masalah komputasi yang dapat dipecahkan dengan menggunakan teknik \emph{brute force}. Seperti sudah kita lihat kebanyakan algoritma yang menggunakan teknik \emph{brute force} ini termasuk ke dalam kelompok algoritma yang memiliki kompleksitas $O(n^2)$. Cara seperti ini tentu saja akan menimbulkan masalah jika jumlah data $n$ yang diolah semakin besar. Seiring dengan pertumbuhan jumlah data, maka waktu \emph{running time} yang dibutuhkan oleh algoritma-algoritma tersebut juga akan semakin tinggi dalam pertumbuhan kuadratik. Untuk itu diperlukan teknik pemecahan masalah komputasi yang lebih baik.

%\dropping{2}{S}
Suatu permasalahan yang semula mudah diselesaikan seringkali menjadi sulit apabila jumlah data yang harus diolah mempunyai ukuran yang berlipat ganda. Apabila penyelesaian masalah dengan data yang berlipat ganda tidak lain adalah penggabungan dari penyelesaian masalah bagian-bagian kecil  yang membangun masalah tersebut, maka masalah yang bersifat demikian dapat dipecahkan dengan teknik \index{divide and conquer@\emph{divide and conquer}} \emph{\textbf{divide and conquer}}.

Berdasarkan kenyataan tersebut, maka penyelesaian masalah dengan teknik divide and conquer dapat dilakukan dengan langkah-langkah berikut:
\begin{itemize}
\item Bagi data menjadi beberapa bagian yang berukuran sama yang dapat dipecahkan dengan cara yang sama.
\item Bila bagian tersebut belum dapat dipecahkan, lakukan hal yang sama yaitu membagi data tersebut menjadi beberapa bagian yang berukuran sama yang dapat dipecahkan dengan cara yang sama, demikian seterusnya.
\item Bila bagian tersebut telah dapat dipecahkan, selesaikan lah masalah tersebut, kemudian gabungkan kembali dengan hasil penyelesaian bagian yang lain, untuk mendapatkan penyelesaian masalah semula. Demikian seterusnya penggabungan tersebut dilakukan hingg didapat penyelesaian dari masalah asal.
\end{itemize}

Gambar~\ref{fig:divide-and-conquer-principle} merupakan diagram yang memperlihatkan prinsip penyelesaian masalah dengan teknik devide and conquer yang membagi data menjadi dua kelompok yang sama, dimana  penyelesaian masalah dari setiap kelompok telah dapat dilakukan.
Berdasarkan cara penyelesaian tersebut terlihat bahwa algoritma yang menggunakan teknik ini akan berupa suatu algoritma yang bersifat rekursif. Berdasarkan hal tersebut maka secara umum running time dari algoritma ini dapat dituliskan sebagai:
\[
 T(n) = a * T(n/b) + f(n)
\]

\begin{figure}
Buat gambar seperti flowchart. Bubble paling atas berlabel `masalah awal dengan jumlah data N'. Bubble ini punya dua anak, bubble kiri dan kanan. Bubble kiri berlabel `sub-masalah 1 dengan jumlah data N/2'. Bubble kanan berlabel `sub-masalah 2 dengan jumlah data N/2'. Di bawah kedua label tadi ada panah ke kotaknya masing-masing berlabel `penyelesaian sub-masalah i'. Lalu di paling akhir ada kotak berlabel `penyelesaian masalah awal'. Diagramnya mirip diagram merge-sort.
\caption{Prinsip penyelesaian masalah dengan teknik devide and conquer.} \label{fig:divide-and-conquer-principle}
\end{figure}

Seperti halnya contoh yang telah dituliskan pada Bab~\ref{ch:analisa-algoritme}, kompleksitas dari algoritma yang mempunyai running time yang bersifat demikian, dapat diturunkan dengan cara menjabarkan $T(n)$ tersebut.


\section{Teorema Master (Master Theorem)}

\index{teorema master@Teorema Master} \index{master theorem@\emph{Master Theorem}} Secara umum untuk mengetahui kompleksitas dari suatu algoritma yang menggunakan teknik devide and conquer dengan menggunakan Teorema Master yang berbunyi sebagai berikut:

Suatu running time yang mempunyai bentuk T(n) = a * T(n/b) + f(n),  dimana f(n) = O(nd),mempunyai kompleksitas:
\[
O(nd)				untuk a < bd
\]
\[
O(nd log n)			untuk a = bd
\]
\[
O(n(log a / log b) )		untuk a > bd
\]

Kembali kepada contoh algoritma pengurutan penggabungan yang running time nya dapat ditulis sebagai:
\[
T(n) = 2*T(n/2) + p*n + q
\]
maka dari running time tersebut dapat diekivalenkan sebagai:
\[
T(n) = a*T(n/b) + f(n)
\]
dimana nilai a = 2, b = 2 dan f(n) = p*n + q = O(n1) sehingga didapat nilai d = 1.

Berdasarkan Teorema Master tersebut, karena a = bd , maka kompleksitas dari algoritma tersebut adalah O(n1 * log n), atau O(n * lg n / lg 2), yang selanjutnya cukup dinyatakan sebagai O(n lg n).


\section{Quick Sort}

Quick Sort merupakan algoritma pengurutan data yang menggunakan teknik  umum untuk mengetahui kompleksitas dari suatu algoritma yang menggunakan teknik devide and conquer. Pada prinsipnya algoritma quick sort akan membagi dua suatu (mempartisi) kumpulan data yang diurutkan atas dasar nilai  pivot yang dipilih. Kumpulan data pertama adalah kumpulan data yang nilainya lebih kecil dari nilai pivot, sedangkan kumpulan kedua adalah kumpulan data yang nilainya lebih besar dari nilai pivot. Data yang bernilai sama dengan nilai pivot diletakkan pada posisi yang tepat, yaitu diantara kedua kumpulan data tersebut. Selanjutnya hal yang sama akan dilakukan pada setiap kelompok data, demikian seterusnya hingga secara keseluruhan data tersebut akan terurut sesuai dengan urutan yang diinginkan

Berdasarkan hal tersebut, maka algoritma quick sort dapat ditulis seperti pada Algoritme~\ref{alg:quick-sort} dan Algoritme~\ref{alg:partition}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE QuickSort (A,p,r)
	\STATE baris 01	Jika ( p < r )
	\STATE baris 02		q = Partition (A,p,r)
	\STATE baris 03		QuickSort (A,p,q-1)
	\STATE baris 04		QuickSort (A,q+1,r)
\end{algorithmic}
\caption{Algoritme Quick Sort.} \label{alg:quick-sort}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE Partition (A,p,r)
	\STATE baris 01	pvt = A[p]
	\STATE baris 02	i = p - 1
	\STATE baris 03	j = r + 1
	\STATE baris 04	Repeat 
	\STATE baris 05		Repeat i = i + 1 Until a[i] >= pvt 
	\STATE baris 06		Repeat j = j + 1 Until a[j] <= pvt 
	\STATE baris 07		Jika i < j  Tukar A[i] dengan A[j]				
	\STATE baris 08	Until i >= j
	\STATE baris 09	Return j
\end{algorithmic}
\caption{Algoritme Partition.} \label{alg:partition}
\end{algorithm}

Kecepatan pelaksanaan algoritma quick sort sangat bergantung kepada susunan data awal. Mengingat bahwa algoritma ini kumpulan awal menjadi dua, maka kondisi terbaik akan terjadi bila pembagian menjadi dua kelompok data masing-masing berjumlah sama banyak. Sebaliknya kondisi terburuk akan terjadi apabila pembagian kelompok yang satu tidak ada anggotanya dan kelompok yang lain beranggota semua data selain pivot dari elemen pivot. 

Berdasarkan hal tersebut, maka running time algoritma quick sort dalam kondisi terbaik adalah T(n) = 2*T (n/2) + O(n), dan dalam kondisi terburuk adalah T(n) = T(n-1) + O(n). Dengan demikian maka dalam kondisi terbaik algoritma quick sort mempunyai kompleksitas O(n*lg n), namun akan mempunyai kompleksitas O(n2) dalam kondisi terburuk.


\section{Pencarian Biner}

Pencarian biner merupakan cara lain yang dapat dipergunakan untuk melakukan pencarian suatu data pada sekumpulan data. Dalam hal ini sekumpulan data harus telah terurut, baik dari terurut dari kecil ke besar (ascending)  maupun besar ke kecil (descending).

Berbeda dengan pencarian sekuensial yang memulai pencarian dari data awal, pencarian biner akan memeriksa data yang berada ditengah. Karena kumpulan data tempat pencarian telah terurut, apabila data yang diperiksa tersebut tidak cocok dengan data yang dicari maka pencarian dapat dilanjutkan dengan salah satu dari kelompok data yang terbagi dua oleh data yang diperiksa, yaitu kelompok yang lebih besar atau yang lebih kecil. Demikian seterusnya hingga ditemukan data yang dicari, atau tidak ada lagi data yang perlu diperiksa. Dengan demikian algoritma dari pencarian biner tersebut dapat ditulis seperti pada Algoritme~\ref{alg:binary-search}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE PencarianBiner (A[0..n-1], bil)
	\STATE baris 01	kr = 0
	\STATE baris 02	kn = n - 1 
	\STATE baris 03	Lakukan selama (kr <= kn )
	\STATE baris 04		tngh = integer ((kr+kn)/2)
	\STATE baris 05		Jika ( A[tngh] = bil ) Return tngh 				
	\STATE baris 06		Jika ( A[tngh] < bil )	
	\STATE baris 07			kn = tngh - 1	
	\STATE baris 08		Jika tidak	
	\STATE baris 09			kr = tngh + 1	
	\STATE baris 10	Return takketemu						
\end{algorithmic}
\caption{Algoritme pencarian biner.} \label{alg:binary-search}
\end{algorithm}

Bila diasumsikan jumlah data adalah n = 2k, maka dari algoritma pencarian biner tersebut dianalisa dapat diketahui bahwa dalam kondisi terburuk, pelaksanaan pernyataan baris 03 sampai dengan 09, akan dilakukan sebanyak k+1 kali. Karena nilai k tidak lain adalah lg n, maka dengan mudah dapat diketahui bahwa running time dari algoritma tersebut akan merupakan fungsi dari lg n, atau kompleksitas dari algoritma tersebut adalah lg n.

Selain teknik pengulangan tersebut, algoritma pencarian biner ini juga dapat dilakukan dengan teknik rekursif, seperti yang terlihat pada Algoritme~\ref{alg:recursive-binary-search}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE PencarianBinerRek (A, awl, akh, bil)
	\STATE baris 01		Jika (awl = akh)				
	\STATE baris 02			Jika ( A[akh] = bil ) Return akh
	\STATE baris 03			Jika tidak Return -1	
	\STATE baris 04		Jika tidak	
	\STATE baris 05			tngh = integer ((awl + akh)/2)
	\STATE baris 06			Jika (A[tngh] = bil) Return tngh
	\STATE baris 07			Jika (A[tngh] > bil)
	\STATE baris 08				akh = tngh - 1
	\STATE baris 09			Jika tidak	
	\STATE baris 10				awl = tngh + 1
	\STATE baris 11			PencarianBinerRek(A,awl,akh,bil)
\end{algorithmic}
\caption{Algoritme pencarian biner rekursif.} \label{alg:recursive-binary-search}
\end{algorithm}


\section{Tinggi Pohon Biner dan traversing pada Pohon Biner}

Seperti telah didefinisikan pada modul terdahulu, tinggi (height) dari suatu tree adalah maksimum depth yang ada pada tree tersebut. Mengingat pada pohon biner selalu mempunyai dua buah sub tree, maka tinggi dari suatu node selalu 1 lebih banyak dari maksimum tinggi dari kedua sub tree tersebut. Berdasarkan hal tersebut algoritma untuk mencari tinggi suatu pohon dapat ditulis seperti pada Algoritme~\ref{alg:tree-height}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE TinggiPohonBiner (T)
	\STATE baris 01		Jika ( T = null ) Return -1				
	\STATE baris 02		tmkr  = TinggiPohonBiner(Tkr) 
	\STATE baris 03		tmkn  = TinggiPohonBiner(Tkn) 
	\STATE baris 04		Return 1 + max(tmkr, tmkn)
\end{algorithmic}
\caption{Algoritma pencarian tinggi pohon biner.} \label{alg:tree-height}
\end{algorithm}

Selain dari pencarian tinggi, hal lain yang sering dilakukan pada pohon biner adalah traversing, yaitu mengunjungi setiap node yang ada pada pohon biner tersebut, untuk kemudian dilakukan operasi tertentu pada node tersebut,. Agar tidak ada satu node pun yang terlewatkan atau sebaliknya ada operasi dilakukan lebih dari satu kali pada node yang sama, maka kunjungan pada node yang ada pada pohon biner harus dilakukan secara sistematis. Hal ini dapat dilakukan dengan tiga cara yaitu: pre-order, in-order dan post-order tarversing.

Pelaksanaan pre-order traversing secara sederhana dapat ditulis sebagai lakukan operasi pada root sebelum mengunjungi (kemudian melakukan operasi yang sama) ke kedua sub tree anak. Berdasarkan hal tersebut, maka algoritma pre-order pada pohon biner dapat ditulis secara rekursif seperti pada Algoritme~\ref{alg:preorder}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE Preorder (T) 
	\STATE baris 01	Jika ( T != null )				
	\STATE baris 02		Proses node
	\STATE baris 03		Preorder (Tkr);
	\STATE baris 04		Preorder (Tkn);
\end{algorithmic}
\caption{Algoritma pre-order traversing.} \label{alg:preorder}
\end{algorithm}


\section{Pencarian dua titik berjarak terdekat secara devide and conquer}

Selain dengan cara brute force, pencarian dua titik berjarak terdekat juga dapat dilakukan dengan teknik devide and conquer. Dengan teknik ini kumpulan titik-titik tersebut terlebih dahulu diurutkan berdasar absis dari titik-titik tersebut. Selanjut kumpulan titik tersebut dibagi menjadi dua kelompok, yaitu kelompok C1 yang absisnya lebih kecil atau sama dengan c, dan kelompok C2 yang absisnya lebih besar dari c. Selanjutnya dari setiap kelompok dicari pasangan titik yang berjarak terdekat, yaitu pasangan pertama dengan jarak d1 dan pasangan pertama dengan jarak d2, untuk kemudian dipilih pasangan titik yang berjarak lebih kecil d = min (d1,d2).
 
Hasil dari langkah tersebut belumlah merupakan jawaban dari permasalahan, karena masih ada kemungkinan pasangan titik lain yang berjarak lebih kecil, yaitu pasangan titik dimana titik pertama ada pada kelompok C1 dan titik kedua ada pada kelompok C2.  Hal ini hanya mungkin terjadi pada titik-titik yang berjarak lebih kecil dari d terhadap garis x = c.

Untuk mencari kemungkinan adanya pasangan titik yang demikian, maka untuk setiap titik P pada kelompok C1 yang berjarak lebih kecil dari d, dilihat apakah ada titik pada kelompok C2 yang berjarak lebih kecil dari d. Kondisi lain yang dalam hal ini perlu dicermati adalah:
\begin{itemize}
\item titik-titik pasangan pada kelompok C2 tersebut mempunyai absis dalam interval [y-d,y+d], dimana y adalah absis titik P.
\item titik-titik pasangan pada kelompok C2 tersebut mempunyai jarak yang lebih besar dari d satu dengan lainnya, dengan demikian maka maksimal hanya ada 6 titik pada kelompok C2 yang bisa jadi berjarak lebih kecil dari d terhadap P.
\end{itemize}

Dengan demikian algoritma yang dapat dipergunakan untuk mencari kemungkinan adanya pasangan titik yang berjarak lebih kecil dari d, adalah mencari titik-titk yang berjarak lebih kecil dari d terhadap garis x = c, dan untuk setiap titik tersebut dilakukan maksimal 6 kali pemeriksaan jarak terhadap titik pasangan yang berada pada kelompok C2. Algoritma ini akan mempunyai kompleksitas O(n).

Berdasarkan analisa diatas, maka running time dari algoitma pencarian dua titik berjarak terdekat secara devide and conquer adalah:
\[
T(n) = 2 * T(n/2) + O(n)
\]
Dengan menggunakan Teorema Master, maka dapat diketahui bahwa kompleksitas dari pencarian dua titik berjarak terdekat secara devide and conquer adalah n lg n.


\section{Algoritma quickhull}

Algoritma quick hull merupakan algoritma untuk membangun convex hull dengan menggunakan teknik devide and conquer. Algoritma ini dibangun berdasarkan kenyataan bahwa convex hull dari sejumlah titik pada bidang datar selalu akan menyertai titik-titik yang berada pada posisi terluar dari bidang datar yang dibentuk.

Berdasarkan kenyataan tersebut, maka titik yang mempunyai absis terkecil P1 dan terbesar Pn akan selalu merupakan titik yang berada garis pembatas convex hull. Dari kedua titik P1 dan Pn dapat ditarik garis P1Pn yang akan membagi dua kelompok titik, yaitu kelompok yang berada dikiri garis tersebut disebut sebagai kelompok S1, dan kelompok yang ada pada dikanan garis P1Pn sebagi kelompok S2.

Selanjutnya pada kelompok S1 dapat dibuat bidang convex hull, yang disebut hull kiri dan pada kelompok S2 dapat dibuat bidang convex hull yang lain yang disebut hull kanan yang keduanya menyertakan titik P1 dan Pn.  Bidang datar yang merupakan convex hull dari permasalahan awal, tidak lain adalah gabungan dari hull kiri dengan hull kanan tersebut.
 
Secara geometri dapat dibuktikan bahwa titik yang terjauh dari garis P1Pn, juga akan merupakan titik terluar dari kelompok tersebut merupakan titik pembangun bidang convex hull. Titik terluar Pm yang merupakan anggota S1 dapat diketahui dengan cara memeriksa luas segitiga P1PnPm. Titik Pm yang memberikan luas maksimum pada segitiga P1PnPm merupakan titik terluar yang dimaksud.

Selanjutnya dengan diketahuinya titik Pm tersebut maka dapat ditarik garis P1Pm yang membagi dua kelompok titik yang ada pada S1 menjadi kelompok S1,1 dan S1,2 serta garis PmPn yang membagi dua kelompok titik yang ada pada S2 menjadi S2,1 dan S2,2.  Selanjutnya dicari lagi titik terluar diantara kelompok tersebut, demikian seterusnya hingga tak ada lagi titik terluar yang perlu dimasukkan sebagai titik pembangun convex hull. 

Mengingat bahwa algoritma quick hull ini selalu membagi dua kelompok titik berdasarkan garis yang didapat, maka running time dari algoritma akan tergantung dari distribusi posisi titik titik semula. Hal ini mirip dengan algoritma quick sort yang running timenya bergantung pada seberapa acak data-data yang akan diurutkan. Karena hal itu maka running time dari algoritma ini dapat diturunkan dengan cara yang sama dengan penurunan running time quick sort. Bila hal tersebut dilakukan, maka akan terlihat bahwa kompleksitas dari algoritma ini sama dengan algoritma quick sort, yaitu n2 dalam kondisi terburuk dan n lg(n) dalam kondisi rata-rata.


\section{Soal-soal latihan dan bahan diskusi}

\begin{Soal}
Tulis algoritma dengan teknik divide and conquer untuk mencari  anggota terbesar dari sekumpulan bilangan integer
\end{Soal}

\begin{Soal}
Perlihatkan pemenggalan dan penggabungan yang terjadi pada algoritma pengurutan penggabungan (merge sort) ketika mengurutkan data berikut: 8, 3, 2, 9, 7, 1, 5 dan 4
\end{Soal}

\begin{Soal}
Ulangi soal no 2 untuk pengurutan cepat (quick sort)
\end{Soal}

\begin{Soal}
Buat algoritma yang dapat menyusun suatu array dengan \(n\) buah bilangan integer, sehingga bilangan kelompok negatif berada di depan kelompok bilangan positif.
\end{Soal}

\begin{Soal}
Tuliskan running time dari algoritma rekursif pencarian biner. Selanjutnya tuliskan kompleksitas dari algoritma tersebut
\end{Soal}

\begin{Soal}
Buat sebuah program untuk mencari tinggi dari suatu pohon biner
\end{Soal}

\begin{Soal}
Tuliskan urutan node yang diselesaikan pada pohon biner pada Gambar~\ref{fig:ex:binary-tree} bila dilakukan traversing secara
\begin{enumerate}
\item preorder
\item inorder
\item postorder
\end{enumerate}
\end{Soal}

\begin{figure}
\begin{center}
Draw a binary tree with a root and its 2 children. Its left child has two children, while its right child has only right child. Label the vertices in BFS-manner a, b, c, d, e, and f.
\end{center}
\caption{Binary Tree} \label{fig:ex:binary-tree}
\end{figure}
